#include<vector>
using namespace std;

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        mergesort(nums,0,nums.size()-1);
        return nums;
    }
    void mergesort(vector<int>&nums , int left, int right){
        if(left >= right)   return;
        int middle = (right-left)/2+left;
        //把左右区间排序
        mergesort(nums,left,middle);
        mergesort(nums,middle+1,right);
        //归并
        int cur1 = left,cur2=middle+1,i = 0;
        vector<int> tmp(right-left+1);
        while(cur1 <= middle && cur2 <= right){
            tmp[i++] = nums[cur1] <nums[cur2] ? nums[cur1++]:nums[cur2++];
        }
        while(cur1 <= middle)   tmp[i++] = nums[cur1++];
        while(cur2 <= right )   tmp[i++] = nums[cur2++];
        //还原
        int j = 0;
        for(int i = left;i <= right;i++){
            nums[i] = tmp[j++];
        }

    }
};
